package nc42;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/9/12 21:21
 * NC42. 加起来和为目标值的组合(二)
 * https://www.nowcoder.com/practice/75e6cd5b85ab41c6a7c43359a74e869a?tpId=196&tqId=37076&ru=/exam/oj
 */
public class Solution {

    public ArrayList<ArrayList<Integer>> combinationSum2 (int[] num, int target) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>(); // 存储返回结果
        ArrayList<Integer> temp = new ArrayList<>(); // 存储每个组合
        // num 先进行预处理, 进行排序便于去重
        Arrays.sort(num);
        // 进行 dfs 穷举排列组合
        dfs(num, target, temp, res, 0);
        // 返回结果
        return res;
    }

    // 回溯 + 剪枝
    private void dfs(int[] num, int target, ArrayList<Integer> temp, ArrayList<ArrayList<Integer>> res, int start) {
        if (target == 0) {
            // 记录结果
            res.add(new ArrayList<>(temp));
        }
        if (start >= num.length) {
            return;
        }
        for (int i = start; i < num.length; i++) {
            if (i > start && num[i - 1] == num[i]) {
                continue; // 去重
            }
            if (num[i] > target) {
                break;
            }
            temp.add(num[i]);
            dfs(num, target - num[i], temp, res, i + 1);
            temp.remove(temp.size() - 1);
        }
    }
}
